package BinarySearch;

/*
    二分查找的变体 findFirstElement
    数组中存在重复的元素，找第一个值等于给定值的元素
 */
public class Variant01 {
    public static void main(String[] args) {

    }

    public static int bSearch(int[] a, int length, int value) {
        int low = 0;
        int high = length - 1;
        while (low <= high) {
            int mid = low + ((low + high) >> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if (a[mid] < value) {
                low = mid + 1;
            } else {
                // mid=0说明已经到了最左边了，那这个元素肯定就是第一个了
                // a[mid-1]!=value如果这句不成立，也就是说前一个元素还是等于value，
                // 那就说明当前mid指向的元素不是第一个值等于value的元素
                if (mid == 0 || a[mid - 1] != value) return mid;
            }
        }
        return -1;//没找到
    }
}
